package com.example.leetcode.trainingcamp.week5.Sunday;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。
 *
 * <p>返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。
 *
 * <p>示例:
 *
 * <p>输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3] 输出: [1, 3] 示例:
 *
 * <p>输入: array1 = [1, 2, 3], array2 = [4, 5, 6] 输出: []
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sum-swap-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer16_21 {
    // array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]   -> [1,3]
    public int[] findSwapValues(int[] array1, int[] array2) {
        int len1 = array1.length;
        Map<Integer,Integer> map = new HashMap<>();
        int sum1 = 0;
        for (int i =0;i<len1;i++){
            sum1 += array1[i];
            map.put(array1[i],i);
        }
        int sum2 = 0;
        for (int item : array2) {
            sum2 += item;
        }
        int abs = Math.abs(sum1 - sum2);
        if (abs % 2 ==1){
            return new int[]{};
        }
        int a = abs / 2;
        if (sum1>sum2){
            for (int value : array2) {
                if (map.containsKey(value + a)) {
                    return new int[]{value + a, value};
                }
            }
            return new int[]{};
        }else if (sum1 < sum2){
            for (int value : array2) {
                if (map.containsKey(value - a)) {
                    return new int[]{value - a, value};
                }
            }
            return new int[]{};
        }else {
            for (int value : array2) {
                if (map.containsKey(value)) {
                    return new int[]{value, value};
                }
            }
            return new int[]{};
        }
    }
}


class TestOffer16_21{
  public static void main(String[] args) {
    int[] array1 = {4,1,2,1,1,2};
    int[] array2 = {3,6,3,3};
    Offer16_21 o = new Offer16_21();
    int[] swapValues = o.findSwapValues(array1, array2);
    System.out.println(swapValues[0]+","+swapValues[1]);
  }
}